package LeetCodeHot100TopInterview;

public class Q055_JumpGame {


    //跳跃游戏
    //每个元素代表你在该位置可以跳跃的最大长度 判断你是否能够到达最后一个下标
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0){
            return false;
        }
        boolean[] dp = new boolean[nums.length];
        return process(nums, 0, dp);
    }

    //大量重复计算 ==> dp傻缓存还不行
    public boolean process(int[] nums, int index, boolean[] dp){
        if (index == nums.length - 1){
            return true;
        }
        if (index > nums.length - 1 || nums[index] == 0){
            return false;
        }

        for (int i = 1; i <= nums[index]; i++) {

            if (!dp[index + i] && process(nums, index + i, dp)){
                dp[index + i] = true;
                return true;
            }
        }
        return false;
    }


    //贪心算法 ==> 如果某位置能抵达 之前所有位置都能抵达 ==> 维持一个最远距离
    public boolean canJump_1(int[] nums) {
        if (nums == null || nums.length == 0){
            return false;
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > max){
                return false;
            }
            max = Math.max(i + nums[i], max);
        }
        return true;
    }


}
